LeetCode 328、奇偶链表

一、题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 奇偶链表（ LeetCode 328 ）:https://leetcode-cn.com/problems/odd-even-linked-list/
class Solution {
    public ListNode oddEvenList(ListNode head) {

        // 边界情况处理，如果链表为空或者只有一个节点，返回 head 就行
        if(head == null || head.next == null ) return head;

        // 设置一个指针，指向链表的头节点，odd 代表奇数节点的头节点
        ListNode odd = head;

        // 设置一个指针，指向链表的头节点的下一个节点，even 代表偶数节点的头节点
        ListNode even = head.next; 

        // 设置一个指针，指向偶数节点的头节点，最终让奇数节点的尾节点的 next 指针指向它
        ListNode evenHead = even;
        
        // 从偶数链表的头节点开始向后遍历
        // 如果当前节点为空，或者后一节点为空，那么说明整个链表已经查看完毕，不需要再遍历了
        while(even != null && even.next != null){
            // 原先奇数节点的下一个节点是偶数节点，即 even 这个节点
            // 根据数学知识，奇数后面一定是偶数，偶数后面一定是奇数
            // 那么 even.next 节点必然是奇数节点
            // 所以让 odd 这个奇数节点的 next 指针指向 even.next 这个奇数节点
            // 这样，odd 上面都是奇数
            odd.next = even.next;
            // 让 odd 移动到最新的由奇数节点组成的链表的尾部位置
            odd = odd.next;

            // 这个时候，odd.next 必然是偶数节点
            // 所以让 even 这个偶数节点的 next 指针指向 odd.next 这个偶数节点
            even.next = odd.next;
            // 让 even 移动到最新的由偶数节点组成的链表的尾部位置
            even = even.next;
        }

        // 此时，原链表所有的节点已经遍历完毕
        // odd 上都是奇数节点
        // even 都是偶数节点
        // 根据题目要求，奇数节点都在偶数节点之前
        // 所以让此时右奇数节点组成的链表的尾部的 next 指针指向由偶数节点组成的链表的头部
        odd.next = evenHead;

        // 最后返回原链表的头部节点就可以了
        // 链表的头部节点没有发生过变化，因为它是奇数节点，并且是第一个奇数节点
        return head;

    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 奇偶链表（ LeetCode 328 ）:https://leetcode-cn.com/problems/odd-even-linked-list/
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        // 边界情况处理，如果链表为空或者只有一个节点，返回 head 就行
        if(head == NULL || head->next == NULL ) return head;

        // 设置一个指针，指向链表的头节点，odd 代表奇数节点的头节点
        ListNode* odd = head;

        // 设置一个指针，指向链表的头节点的下一个节点，even 代表偶数节点的头节点
        ListNode* even = head->next; 

        // 设置一个指针，指向偶数节点的头节点，最终让奇数节点的尾节点的 next 指针指向它
        ListNode* evenHead = even;
        
        // 从偶数链表的头节点开始向后遍历
        // 如果当前节点为空，或者后一节点为空，那么说明整个链表已经查看完毕，不需要再遍历了
        while(even != NULL && even->next != NULL){
            // 原先奇数节点的下一个节点是偶数节点，即 even 这个节点
            // 根据数学知识，奇数后面一定是偶数，偶数后面一定是奇数
            // 那么 even->next 节点必然是奇数节点
            // 所以让 odd 这个奇数节点的 next 指针指向 even->next 这个奇数节点
            // 这样，odd 上面都是奇数
            odd->next = even->next;
            // 让 odd 移动到最新的由奇数节点组成的链表的尾部位置
            odd = odd->next;

            // 这个时候，odd->next 必然是偶数节点
            // 所以让 even 这个偶数节点的 next 指针指向 odd->next 这个偶数节点
            even->next = odd->next;
            // 让 even 移动到最新的由偶数节点组成的链表的尾部位置
            even = even->next;
        }

        // 此时，原链表所有的节点已经遍历完毕
        // odd 上都是奇数节点
        // even 都是偶数节点
        // 根据题目要求，奇数节点都在偶数节点之前
        // 所以让此时右奇数节点组成的链表的尾部的 next 指针指向由偶数节点组成的链表的头部
        odd->next = evenHead;

        // 最后返回原链表的头部节点就可以了
        // 链表的头部节点没有发生过变化，因为它是奇数节点，并且是第一个奇数节点
        return head;
    }
};

3、Python 代码

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 边界情况处理，如果链表为空或者只有一个节点，返回 head 就行
        if head == None or head.next == None :
           return head

        # 设置一个指针，指向链表的头节点，odd 代表奇数节点的头节点
        odd = head

        # 设置一个指针，指向链表的头节点的下一个节点，even 代表偶数节点的头节点
        even = head.next 

        # 设置一个指针，指向偶数节点的头节点，最终让奇数节点的尾节点的 next 指针指向它
        evenHead = even
        
        # 从偶数链表的头节点开始向后遍历
        # 如果当前节点为空，或者后一节点为空，那么说明整个链表已经查看完毕，不需要再遍历了
        while even != None and even.next != None :
            # 原先奇数节点的下一个节点是偶数节点，即 even 这个节点
            # 根据数学知识，奇数后面一定是偶数，偶数后面一定是奇数
            # 那么 even.next 节点必然是奇数节点
            # 所以让 odd 这个奇数节点的 next 指针指向 even.next 这个奇数节点
            # 这样，odd 上面都是奇数
            odd.next = even.next
            # 让 odd 移动到最新的由奇数节点组成的链表的尾部位置
            odd = odd.next

            # 这个时候，odd.next 必然是偶数节点
            # 所以让 even 这个偶数节点的 next 指针指向 odd.next 这个偶数节点
            even.next = odd.next
            # 让 even 移动到最新的由偶数节点组成的链表的尾部位置
            even = even.next
        

        # 此时，原链表所有的节点已经遍历完毕
        # odd 上都是奇数节点
        # even 都是偶数节点
        # 根据题目要求，奇数节点都在偶数节点之前
        # 所以让此时右奇数节点组成的链表的尾部的 next 指针指向由偶数节点组成的链表的头部
        odd.next = evenHead

        # 最后返回原链表的头部节点就可以了
        # 链表的头部节点没有发生过变化，因为它是奇数节点，并且是第一个奇数节点
        return head

四、复杂度分析

时间复杂度：O(n)，其中 n 是链表的节点数。需要遍历链表中的每个节点，并更新指针。

空间复杂度：O(1)。只需要维护有限的指针。